The present invention relates to programming systems and more particularly to query implementation.
In modern programming systems, it is a common task to query method metadata given a code address (or an instruction pointer (IP)). For instance, identifying a method handle for a specific frame during stack unwinding and locating method symbols by a sampling-based profiler are typical representative usages. The efficiency of query implementation is essential to system performance, especially for managed runtime environments (MRTEs), where the lookup time is part of runtime.
Conventional query implementation typically employs a data structure, such as a method lookup table, to save the starting and ending addresses of each method after a compiler generates its code. The data structure may be a linear sorted array or other structure that minimizes search time.
While this mechanism works well for traditional static or runtime environments on desktops and servers, problems exist in extending the mechanism to emerging mobile platforms such as cellular telephones and personal digital assistants (PDAs). These problems include a burden in terms of search and maintenance for small footprint systems, as the size of a method lookup table is proportional to the number of compiled methods; and runtime searching within the table is not as efficient in mobile systems as in desktop and server environments. Further, allocation and recycling of code in managed space introduces considerable complexity in maintaining [start address, end address] tuples. This is because the starting and ending addresses for a specific method may be changed or even invalidated if a garbage collector reclaims the method's code. Thus a need exists to store and query method metadata more efficiently, particularly in managed runtime environments.